package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 2115. 从给定原材料中找到所有可以做出的菜
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/5 13:37
 */
public class FindAllRecipes {


    public static void main(String[] args) {
        FindAllRecipes test = new FindAllRecipes();

        // {"bread"}
        String[] recipes = {"bread"};
        List<List<String>> ingredients = new ArrayList<>();
        ingredients.add(Arrays.asList("yeast", "flour"));
        String[] supplies = {"yeast", "flour", "corn"};

        // {"bread","sandwich"}
//        String[] recipes = {"bread","sandwich"};
//        List<List<String>> ingredients = new ArrayList<>();
//        ingredients.add(Arrays.asList("yeast","flour"));
//        ingredients.add(Arrays.asList("bread","meat"));
//        String[] supplies = {"yeast","flour","meat"};

        // {"bread","sandwich","burger"}
//        String[] recipes = {"bread","sandwich","burger"};
//        List<List<String>> ingredients = new ArrayList<>();
//        ingredients.add(Arrays.asList("yeast","flour"));
//        ingredients.add(Arrays.asList("bread","meat"));
//        ingredients.add(Arrays.asList("sandwich","meat","bread"));
//        String[] supplies = {"yeast","flour","meat"};

        // {}
//        String[] recipes = {"bread"};
//        List<List<String>> ingredients = new ArrayList<>();
//        ingredients.add(Arrays.asList("yeast","flour"));;
//        String[] supplies = {"yeast"};

        // [q, fzjnm, ju]
//        String[] recipes = {"ju","fzjnm","x","e","zpmcz","h","q"};
//        List<List<String>> ingredients = new ArrayList<>();
//        ingredients.add(Arrays.asList("d"));
//        ingredients.add(Arrays.asList("hveml","f","cpivl"));
//        ingredients.add(Arrays.asList("cpivl","zpmcz","h","e","fzjnm","ju"));
//        ingredients.add(Arrays.asList("cpivl","hveml","zpmcz","ju","h"));
//        ingredients.add(Arrays.asList("h","fzjnm","e","q","x"));
//        ingredients.add(Arrays.asList("d","hveml","cpivl","q","zpmcz","ju","e","x"));
//        ingredients.add(Arrays.asList("f","hveml","cpivl"));
//        String[] supplies = {"f","hveml","cpivl","d"};

        List<String> allRecipes = test.findAllRecipes(recipes, ingredients, supplies);
        System.out.println(allRecipes);
    }

    private Map<String, List<String>> map = new HashMap<>();
    private Map<String, Boolean> flags = new HashMap<>();
    private Set<String> set = new HashSet<>();
    private Set<String> run = new HashSet<>();


    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        int length = recipes.length;
        for (int i = 0; i < length; i++) {
            map.put(recipes[i], ingredients.get(i));
        }
        Collections.addAll(set, supplies);
        for (String recipe : recipes) {
            find(recipe);
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Boolean> entry : flags.entrySet()) {
            if (entry.getValue()) {
                list.add(entry.getKey());
            }
        }
        return list;
    }

    private boolean find(String key) {
        if (run.contains(key)) {
            flags.put(key, false);
            return false;
        }
        run.add(key);
        Boolean flag = flags.get(key);
        if (flag != null) {
            run.remove(key);
            return flag;
        }
        List<String> list = map.get(key);
        for (String s : list) {
            if (set.contains(s)) {
                continue;
            }
            List<String> li = map.get(s);
            if (li == null) {
                flags.put(key, false);
                run.remove(key);
                return false;
            }
            Boolean f = flags.get(s);
            if (f != null) {
                if (f) {
                    continue;
                }
                flags.put(key, false);
                run.remove(key);
                return false;
            }
            if (!find(s)) {
                flags.put(key, false);
                run.remove(key);
                return false;
            }
        }
        flags.put(key, true);
        run.remove(key);
        return true;
    }

}
